package leetcode_400;

import java.util.Arrays;
import java.util.Comparator;

/**
 *@author 周杨
 *RussianDollEnvelopes_354 给定二维数组 表示信封的长和宽 求最大的信封能装几个小信封
 *describe:用比较器先排序 后再用动态规划求最大增长子序列 AC 41%
 *2018年7月8日 下午1:48:37
 */
public class RussianDollEnvelopes_354 {

	public static void main(String[] args) {
		RussianDollEnvelopes_354 test=new RussianDollEnvelopes_354();
		int[][] envelopes =new int[][] {{46,89},{50,53},{52,68},{72,45},{77,81}};
		System.out.println(test.maxEnvelopes(envelopes));
	}
	
	public int maxEnvelopes(int[][] envelopes) {
		if(envelopes.length==0||envelopes[0].length==0)
        	return 0;
       Arrays.sort(envelopes, new Comparator<int[]>() {
            @Override
            public int compare(int[] e1, int[] e2) {
                if (e1[0] != e2[0]) return e1[0] - e2[0];
                return e1[1] - e2[1];
            }
        });
        int dp[]=new int[envelopes.length];
        dp[0]=1;
        int res=1;
        for(int i=1;i<envelopes.length;++i) {
        	for(int j=0;j<i;++j) {
        		if(envelopes[i][0]>envelopes[j][0]&&
        				envelopes[i][1]>envelopes[j][1]) {
        			dp[i]=Math.max(1+dp[j], dp[i]);
        			res=Math.max(dp[i], res);
        		}	
        	}
        	if(dp[i]==0)
        		dp[i]=1;
        }
        return res;
    }

}
